package leetcode_401_500;

import java.util.*;

public class LeeCode_451 {
    public static void main(String[] args) {

    }
    private static String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }
        TreeMap<Integer, List<Character>> tree = new TreeMap<>();
        for (Character key : map.keySet()) {
            int c = map.get(key);
            if (tree.containsKey(c)){
                tree.get(c).add(key);
            }else {
                List<Character> list = new ArrayList<>();
                list.add(key);
                tree.put(c, list);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (Integer key : tree.keySet()) {
            List<Character> list = tree.get(key);
            for (Character c : list) {
                for (int i = 0; i < key; i++) {
                    sb.append(c);
                }
            }
        }
        return sb.reverse().toString();
    }
}
